/**
 * Largest Rectangle in Histogram
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.


Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].


The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.
 */
package com.xinpan.exercise;

import java.util.Stack;

public class LargestRectangleArea {
	//no sure why this one is wrong
    public int largestRectangleArea(int[] height) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(height.length == 0)
            return 0;
        
        int start=0;
        int end=0;
        int len = height.length;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < len; i++)
        {
            int min = height[i];
            for(int j = i; j < len; j++)
            {
                if(height[j] < min)
                    min = height[j];
                if(min * (len-i) <= max)
                    break;
                if(min * (j-i+1) > max)
                {
                	 max = min * (j-i+1);
                	 start = i;
                	 end = j;
                }
                   
            }
        }
        System.out.println(start + ":"+ end);
        return max;
    }
    
    
    public int largestRectangleArea2(int[] height) {
        // Start typing your Java solution below
        // DO NOT write main() function
    
    
    Stack<Integer> bars = new Stack<Integer>();
    
    int[] wid = new int[height.length];
    
    for(int i = 0; i < height.length; i++)
    {
        while(bars.size() > 0  && height[i] <= height[bars.peek()]) bars.pop();
        
        int j = bars.size() == 0 ? 0 : bars.peek()+1;
        bars.push(i);
        wid[i] = i-j;
    }
    bars.clear();
    
    for(int i = height.length-1; i >= 0; i--)
    {
        while(bars.size() > 0 && height[i] <= height[bars.peek()]) bars.pop();
        int j = bars.size() == 0 ? height.length-1 : bars.peek()-1;
        bars.push(i);
        wid[i] += j- i + 1;
    }
    
    int max = 0;
    for(int i = 0; i < height.length; i++)
    {
        if(height[i] * wid[i] > max)
            max = height[i] * wid[i];
    }
    return max;
    }
    
    public static void main(String[] args)
    {
    	int[] in = {2,4};
    	LargestRectangleArea lra = new LargestRectangleArea();
    	System.out.println(lra.largestRectangleArea2(in));
    }
}
